package org.example.myleet.rosalind.sign;

import org.example.myleet.rosalind.utils.BigNumberOperator;
import org.example.myleet.rosalind.utils.PermutationUtil;

import java.io.File;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.List;

public class Solution {

    public static void main(String[] args) {
        Solution solution = new Solution();
//        solution.findAllSignPermutations(2);
//        solution.findAllSignPermutations(3);
        solution.findAllSignPermutations(6);
    }

    private int totalCount;

    public void findAllSignPermutations(int n) {
        Solution solution = new Solution();
        totalCount = 0;
        int permCount = BigNumberOperator.factorial(n).intValue();
        int signCount = 1;
        for (int i = 0; i < n; ++i) {
            signCount *= 2;
        }
        List<String> res = new ArrayList<>(permCount * signCount);
        //false - positive, true - negative
        boolean[] sign = new boolean[n];
        int[] permutation = new int[n];
        for (int i = 1; i <= n; ++i) {
            permutation[i - 1] = i;
        }
        backtrackForSign(permutation, sign, 0, res);
        int[] nextPermutation = PermutationUtil.nextPermutation(permutation);
        do {
            backtrackForSign(nextPermutation, sign, 0, res);
            permutation = nextPermutation;
            nextPermutation = PermutationUtil.nextPermutation(permutation);
        } while (PermutationUtil.hasNextPermutation(permutation, nextPermutation));
        String path = solution.getClass().getResource("").getPath() + "output.txt";
        File outputFile = new File(path);
        if (outputFile.exists()) {
            outputFile.delete();
        }
        OutputStream os = null;
        try {
            outputFile.createNewFile();
            os = new FileOutputStream(outputFile);
            os.write((totalCount + "\n").getBytes());
            for (String line : res) {
                os.write(line.getBytes());
                os.write("\n".getBytes());
            }
        } catch (IOException e) {
            e.printStackTrace();
        } finally {
            if (os != null) {
                try {
                    os.flush();
                    os.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    private void backtrackForSign(int[] permutation, boolean[] sign, int i, List<String> res) {
        if (i >= permutation.length) {
            String perm = arrayToString(permutation, sign);
            res.add(perm);
            ++totalCount;
            return;
        }
        sign[i] = true;
        backtrackForSign(permutation, sign, i + 1, res);
        sign[i] = false;
        backtrackForSign(permutation, sign, i + 1, res);
    }

    private String arrayToString(int[] permutation, boolean[] sign) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < permutation.length; ++i) {
            if (sign[i]) {
                sb.append('-');
            }
            sb.append(permutation[i]).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        return sb.toString();
    }
}
